#
# @lc app=leetcode.cn id=118 lang=python3
#
# [118] 杨辉三角
#
from typing import List


# @lc code=start
class Solution:
    def generate1(self, numRows: int) -> List[List[int]]:
        def factorial(n):
            if n == 0:
                return 1
            return n * factorial(n - 1)

        def C(n, m):
            return round(factorial(n) / factorial(n - m) / factorial(m))

        ret = []
        for i in range(numRows):
            ret.append([])
            for j in range(i + 1):
                ret[-1].append(C(i, j))

        return ret

    def generate(self, numRows: int) -> List[List[int]]:
        ret = []
        for i in range(numRows):
            ret.append([])
            for j in range(i + 1):
                if j == 0 or j == i:
                    ret[-1].append(1)
                else:
                    ret[-1].append(ret[-2][j - 1] + ret[-2][j])
        return ret

# @lc code=end

if __name__ == "__main__":
    s = Solution()

    print(s.generate(5))
